package com.example.demo.utils;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname MaxPQ
 * @description
 * @date 2023/04/09 10:27
 * <p>
 * ******************************************************
 */
public class MaxPQ<E extends Comparable<E>> {

    // 存储元素的数组
    private E[] pq;
    // 当前 Priority Queue 中的元素个数
    private int size = 0;

    public MaxPQ(int cap) {
        // 索引 0 不用，所以多分配一个空间
        pq = (E[]) new Comparable[cap + 1];
    }

    /* 返回当前队列中最大元素 */
    public E max() {
        return pq[1];
    }

    /* 插入元素 e */
    public void insert(E e) {
        size++;
        // 先把新元素加到最后
        pq[size] = e;
        swim(size);
    }

    /* 删除并返回当前队列中最大元素 */
    public E delMax() {
        // 堆顶元素就是最大值
        E e = pq[1];
        // 交换起始两个元素位置
        swap(1, size);
        pq[size] = null;
        size--;
        sink(1);
        return e;
    }

    /* 上浮第 x 个元素，以维护最大堆性质 */
    private void swim(int x) {
        // 如果下标是子节点，就判断一直上浮，直到为根节点
        while (x > 1 && less(parent(x), x)) {
            swap(parent(x), x);
            x = parent(x);
        }
    }

    /* 下沉第 x 个元素，以维护最大堆性质 */
    private void sink(int x) {
        // 如果下标是根节点，就判断一直下沉，直到为叶子节点
        // 对比size是为了判断该节点指针是否存在
        while (left(x) <= size) {
            int max = left(x);
            if (right(x) <= size && less(max, right(x))) {
                max = right(x);
            }
            // 如果当前节点比子节点都大，就没必要下沉了
            if (less(max, x)) break;
            // 否则，不符合最大堆的结构，下沉 x 结点
            swap(max, x);
            x = max;
        }
    }

    /* 交换数组的两个元素 */
    private void swap(int i, int j) {
        E temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    /* pq[i] 是否比 pq[j] 小？ */
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    // 父节点的索引
    int parent(int root) {
        return root / 2;
    }

    // 左孩子的索引
    int left(int root) {
        return root * 2;
    }

    // 右孩子的索引
    int right(int root) {
        return root * 2 + 1;
    }


}
